本文持续更新中
0X00 前置知识
LCT 的前置知识有:Splay(网上有用 fhq-Treap 写 LCT 的方法,不主流,在这里不作讲解)
0X01 介绍
LCT(Link-Cut Tree),是一个 Splay 森林。Splay 之间用虚边连接,Splay 内部用实边连接。
LCT的一些经典操作有:
- 连接树边
- 删除树边
- 链上操作,如修改、询问链上权值
0X02 基本定义
int fa[MAXN], v[MAXN], s[MAXN], tag[MAXN], st[MAXN], son[MAXN][2];
fa 存每个节点的父亲,v 是点权,s 是该点以及子树的权值和,tag 是该点的翻转情况,st 是一个栈,将在下文提到,son 存左右儿子。
0X03 基本操作
咕了